public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }

    /**
     * x的n次方
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        if(x==0){
            return 0;
        }
        int left=1,right=x;
        while(left<right){
            int mid=left+(right-left+1)/2;
            if((long)mid*mid<=x){
                left=mid;
            }
            else{
                right=mid-1;
            }
        }
        return left;
    }
    /**
     * 搜索插入位置
     */
    public int mySqrt2(int x) {
        if(x==0){
            return 0;
        }
        int left=1,right=x;
        while(left<right){
            int mid=left+(right-left+1)/2;
            if((long)mid*mid<=x){
                left=mid;
            }
            else{
                right=mid-1;
            }
        }
        return left;
    }

    /**
     * 山脉数组的峰顶索引
     * @param arr
     * @return
     */
    public int peakIndexInMountainArray(int[] arr) {
        int n=arr.length;
        int left=0,right=n-1;
        while(left<right){
            int mid=left+(right-left+1)/2;
            if(arr[mid]>arr[mid-1]){
                left=mid;
            }
            else{
                right=mid-1;
            }
        }
        return left;
    }
    /**
     * 寻找峰值
     */
    public int findPeakElement(int[] nums) {
        int n=nums.length;
        int left=0,right=n-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<nums[mid+1]) left=mid+1;
            else right=mid;
        }
        return left;
    }
    /**
     * 搜索旋转排序数组中最小值
     */
    public int findMin(int[] nums) {
        int n=nums.length;
        int left=0,right=n-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[right]) left=mid+1;
            else right=mid;
        }
        return nums[left];
    }
}